#pragma once

#include <boost/assert.hpp>
#include <boost/static_assert.hpp>

// Required for multithreaded/singlethreaded policy
#include "../policies.hpp"

#include "../smart_ptr.hpp"

// Defines in read/write buffering policies, brings auto_list
#include "queue_policies.hpp"


// Uncomment the following line of you want copy-constructing of queues to be enabled
//#define BOOST_PLUS_ENABLE_QUEUE_COPYING

// Uncomment the following line if you want assigning queues to be enabled
//#define BOOST_PLUS_ENABLE_QUEUE_ASSIGNING




namespace boostext
{
	/**
	 * @brief   queue is a template container adaptor class that implements a multiple writers, multiple readers queue.
	 *
	 * Depending on the policy, the queue can even be used in multithreaded applications. Due to a special
	 * list container adaptor, pushing / popping multiple elements to/from the queue doesn't involve copy
	 * constructing any value, instead the list nodes are spliced onto/from the queue.
	 *
	 * When it comes to modifying the queue, a special reader & writer classes can be used.
	 *
	 * @warning   When a queue is being copy-constructed, all values on the queue are copied to the new one.
	 *            Readers & writers that have been created on the previous queue will know nothing about the
	 *            new one. To be able to use the new queue, create a reader/ writer on the new one.
	 */
	template
	<
		typename _Ty,
		class threading_policy = multithreaded
	>
	class queue
	{
	public:

		typedef threading_policy                TP;

		typedef typename boost::optional<_Ty>   _Opt_Ty;
		typedef typename auto_list<_Ty>         _List_Ty;

		typedef typename _List_Ty::size_type    size_type;

		typedef typename queue<_Ty>             _Queue;

	private:

		/**
		 * This is the actual implementation of the queue.
		 * It is shared amongst the queue, their readers and writers.
		 * Implementing it this way helps to identify dead queues, but
		 * still existing readers/writers.
		 */
		class queue_private
			: public threading_policy
		{
		private:

			_List_Ty             _q;
			volatile size_type   _size;

		public:

			queue_private()
				: _size(0)
			{}

			queue_private(queue_private& _Right)
			{
				// We don't need to lock ourselves: We're just being constructed
				// But the other one must be locked for reading
				TP::read_lock lock(_Right);

				// Make a true copy of the right queue's storage and
				// move it onto our storage.
				std::list<_Ty> tmp = _Right._q.storage();
				_q    = tmp;
				_size = _Right._size;
			}



			queue_private& operator=(queue_private& _Right)
			{
				// We must be locked for writing
				TP::write_lock lock(*this);

				// The other one must be locked for reading
				TP::read_lock lock(_Right);

				// Make a true copy of the right queue's storage and
				// move it onto our storage.
				std::list<_Ty> tmp = _Right._q.storage();
				_q    = tmp;
				_size = _Right._size;
			}



			void push(const _Ty& _Val)
			{
				TP::write_lock lock(*this);

				_q.push_back(_Val);
				++_size;
			}

			void push(_List_Ty& _Vals)
			{
				// Don't bother locking when there's nothing to be pushed
				if(_Vals.empty())
					return;

				TP::write_lock lock(*this);

				// This one must be done BEFORE splicing, otherwise the size doesn't increment
				_size += _Vals.size();
				_q.splice(_q.end(), _Vals);
			}

			_Opt_Ty pop()
			{
				TP::write_lock lock(*this);

				if(!_q.empty())
				{
					_Opt_Ty ret(_q.front());
					_q.pop_front();
					--_size;

					return ret;
				}
				else
				{
					return _Opt_Ty();
				}
			}

			_List_Ty pop(size_t _Count)
			{
				// Don't bother locking when nothing should be popped
				if(!_Count)
					return _List_Ty();

				TP::write_lock lock(*this);

				if(!_q.empty())
				{
					auto_list<_Ty> ret;

					// Remove up to 'count' elements from the queue and return them.
					// We can use the ultra fast splice function for that
					_Count = (_Count > _q.size()) ? _q.size() : _Count;
					_List_Ty::iterator first = _q.begin();
					_List_Ty::iterator last = first;
					std::advance(last, _Count);

					ret.splice(ret.end(), _q, first, last);
					_size -= _Count;

					return ret;
				}
				else
				{
					return _List_Ty();
				}
			}

			_List_Ty pop_all()
			{
				TP::write_lock lock(*this);

				if(!_q.empty())
				{
					_List_Ty ret = _q;
					_size = 0;

					return ret;
				}
				else
				{
					return _List_Ty();
				}
			}

			_Opt_Ty peek() const
			{
				TP::read_lock lock(*this);

				if( !_q.empty() )
				{
					return _Opt_Ty(_q.front());
				}
				else
				{
					return _Opt_Ty();
				}
			}

			size_type size()
			{
				TP::read_lock lock(*this);

				return _q.size();
			}

			size_type sizeHint() const
			{
				return _size;
			}
		};
		///////////////////////////////////////////////////////////////////////////////////////////

		typedef smart_ptr<queue_private>   queue_ptr;

	public:

		/**
		 * A writer may only push values onto the queue. It
		 * can not retrieve the size of the queue, nor can it
		 * pop/peek values.
		 *
		 * A writer is obtained by calling queue::writer().
		 */
		template
		<
			template <typename> class buffering_policy = write_buffered
		>
		class queue_writer
			: public buffering_policy<_Ty>
		{
		public:

			typedef buffering_policy<_Ty>   BP;

		public:

			/**
			 * Create a writer that writes to this queue.
			 * It operates on the private implementation of the queue, that is shared
			 * with this writer (and any other writer for that matter).
			 */
			queue_writer(const queue_ptr &d)
				: d(d)
			{}

			/**
			 * Create a writer from another writer.
			 * It operates on the same queue than _Right.
			 */
			queue_writer( queue_writer<buffering_policy> &_Right )
				: BP(_Right)
				, d(_Right.d)
			{}

			/**
			 * Create a writer from another writer.
			 * It operates on the same queue than _Right.
			 * Can even be created from a writer that uses different policies, but
			 * this depends on the policies used.
			 */
			template
			<
				template <typename> class buffering_policy
			>
			queue_writer( queue_writer<buffering_policy> &_Right )
				: BP(_Right)
				, d(_Right.d)
			{}



			/**
			 * Flush the buffer manually
			 */
			void flush()
			{
				_flush<BP::buffered>();
			}



			/**
			 * Push an element onto the queue.
			 */
			void push(const _Ty& _Val)
			{
				_push<BP::buffered>(_Val);
			}

			/**
			 * Push a number of elements onto the queue.
			 */
			void push(_List_Ty& _Vals)
			{
				_push<BP::buffered>(_Vals);
			}

		private:

			/**
			 * Dummy for unbuffered policy.
			 */
			template <bool unbuffered>
			void _flush()
			{}

			/**
			 * Flush the buffer.
			 */
			template <>
			void _flush<true>()
			{
				// Don't lock the queue when the buffer is empty
				if(!BP::empty())
				{
					d->push(BP::flushBuffer());
				}
			}

			/**
			 * Directly push an element onto the queue.
			 */
			template <bool unbuffered>
			void _push(const _Ty& _Val)
			{
				d->push(_Val);
			}

			/**
			 * Push an element onto the buffer and flush it when told to.
			 */
			template <>
			void _push<true>(const _Ty& _Val)
			{
				BP::push(_Val);
				if(BP::mustFlush())
				{
					d->push(BP::flushBuffer());
				}
			}

			/**
			 * Push an multiple elements directly onto the queue.
			 */
			template <bool unbuffered>
			void _push(_List_Ty& _Vals)
			{
				d->push(_Vals);
			}

			/**
			 * Push multiple elements onto the buffer and flush it when told to.
			 */
			template <>
			void _push<true>(_List_Ty& _Vals)
			{
				BP::push(_Vals);
				if(BP::mustFlush())
				{
					d->push(BP::flushBuffer());
				}
			}

		private:

			queue_ptr   d;
		};
		///////////////////////////////////////////////////////////////////////////////////////////

		typedef queue_writer<write_unbuffered> unbuffered_writer;
		typedef queue_writer<write_buffered>   buffered_writer;




		/**
		 * A reader may retrieve the first item (pop), look at the first one (peek)
		 * and query the size of the queue (size,sizeGuess).
		 *
		 * A reader is obtained by calling queue::reader().
		 */
		template
		<
			template <typename> class buffering_policy = read_buffered
		>
		class queue_reader
			: public buffering_policy<_Ty>
		{
		public:

			typedef typename buffering_policy<_Ty>   BP;
			typedef typename std::size_t             size_type;

		public:

			/**
			 * Create a queue_reader that reads from the given queue.
			 */
			queue_reader( const queue_ptr &d )
				: d(d)
			{}

			/**
			 * Create a reader from another one.
			 * The reader operates on the same queue as the copied one.
			 */
			queue_reader( queue_reader<buffering_policy> &_Right )
				: BP(_Right)
				, d(_Right.d)
			{}

			/**
			 * Create a reader from another one.
			 * The reader operates on the same queue as the copied one.
			 * Can even be created from a reader with different policies, but this
			 * depends on the policies used.
			 */
			template
			<
				template <typename> class buffering_policy
			>
			queue_reader( queue_reader<buffering_policy> &_Right )
				: BP(_Right)
				, d(_Right.d)
			{}



			/**
			 * Retrieve and remove the first element from the queue.
			 *
			 * @return   the first element, if the queue is not empty
			 * @return   an empty boost::optional<T>, if the queue is empty
			 */
			_Opt_Ty pop()
			{
				return pop<BP::buffered>();
			}

			/**
			 * Retrieve and remove up to '_Count' elements from the queue.
			 *
			 * @return   an auto_list with up to 'count' elements, when it is not empty
			 * @return   an empty auto_list when the queue is empty
			 */
			_List_Ty pop(size_type _Count)
			{
				return pop<BP::buffered>(_Count);
			}

			/**
			 * Retrieve and remove all elements from the queue.
			 *
			 * @return   a auto_list containing the entire queue, when it is not empty
			 * @return   an empty auto_list when the queue is empty
			 */
			_List_Ty pop_all()
			{
				// There is no point in buffering this:
				// All elements are removed from the queue, it's as simple as that.
				return d->pop_all();
			}

			/**
			* Get a look at the first element of the queue. It stays in the queue.
			*
			* @return   the first element of the queue, when it is not empty
			* @return   an empty boost:optional<T> when the queue is empty
			*/
			_Opt_Ty peek()
			{
				// This one is not buffered as well: It makes no sense and would
				// screw-up the buffer.
				return d->peek();
			}

			/**
			 * Get the number of elements in the queue.
			 */
			size_type size()
			{
				// When there's a buffer in place, the actual size of the queue
				// might not reflect the size, as it is visible to the reader.
				return size<BP::buffered>();
			}

			/**
			* Get the possible number of elements in the queue.
			* The value returned may differ from the actual number, at the
			* time of calling.
			*/
			size_type sizeHint() const
			{
				// When there's a buffer in place, the actual size of the queue
				// might not reflect the size, as it is visible to the reader.
				return sizeHint<BP::buffered>();
			}

		protected:

			/**
			 * Pop an element directly from the queue.
			 */
			template <bool unbuffered>
			_Opt_Ty pop()
			{
				return d->pop();
			}

			/**
			 * Pop an element from the buffer.
			 * The buffer is filled with up to BP::batchSize elements, when it's
			 * empty, prior to pop().
			 */
			template <>
			_Opt_Ty pop<true>()
			{
				// Don't use the buffer when it's batchSize has been set to 0.
				if(BP::batchSize() == 0)
					return d->pop();

				// When the buffer is empty, fill it again, but
				// only try to fill it, if the queue contains elements.
				if(BP::empty())
				{
					if(d->sizeHint())
						BP::fillBuffer(d->pop(BP::batchSize()));
					else
						return _Opt_Ty();
				}

				// Now pop the first element from the buffer
				return BP::pop();
			}

			/**
			 * Pop a number of elements directly from the queue.
			 */
			template <bool unbuffered>
			_List_Ty pop(size_type _Count)
			{
				return d->pop(_Count);
			}

			/**
			 * Pop a number of elements from the buffer.
			 * The buffer is filled with as many items, to satisfy _Count,
			 * prior to pop().
			 */
			template <>
			_List_Ty pop<true>(size_type _Count)
			{
				// When the size of the buffer is not enough, try to pop as many elements from the
				// queue, to satisfy _Count.
				if(_Count > BP::size())
				{
					// Only try to pop elements from the queue, if it contains elements.
					if(d->sizeHint())
						BP::fillBuffer(d->pop(_Count - BP::batchSize()));
				}

				// We've done all we can, now return that many elements from the buffer.
				return BP::pop(_Count);
			}

			/**
			 * Get the size of the queue.
			 */
			template <bool unbuffered>
			size_type size() const
			{
				return d->size();
			}

			/**
			 * Get the size of the queue.
			 * It's size, visible to the user of queue_reader will be
			 * the queue's actual size, plus the buffer size.
			 */
			template <>
			size_type size<true>() const
			{
				return BP::size() + d->size();
			}

			/**
			 * Get a hint about the size of the queue.
			 */
			template <bool unbuffered>
			size_type sizeHint() const
			{
				return d->size();
			}

			/**
			 * Get a hint about the size of the queue.
			 * It's size, visible to the user of queue_reader will be
			 * the queue's actual size, plus the buffer size.
			 */
			template <>
			size_type sizeHint<true>() const
			{
				return BP::size() + d->sizeHint();
			}

		private:

			queue_ptr   d;
		};
		///////////////////////////////////////////////////////////////////////////////////////////////

		typedef queue_reader<read_unbuffered>   unbuffered_reader;
		typedef queue_reader<read_buffered>     buffered_reader;

	public:

		/**
		 * Create an empty queue.
		 */
		queue()
			: d(new queue_private)
		{}

		/**
		 * Construct a queue from another one.
		 * The entire queue's contents will be copied,
		 * however whatever is in the buffer of a reader/writer
		 * will \b not be copied.
		 */
		#ifdef BOOST_PLUS_ENABLE_QUEUE_COPYING
		queue(queue<_Ty,threading_policy>& _Right)
		{
			*this = _Right;
		}
		#else
		queue(queue<_Ty,threading_policy>& _Right)
		{
			// Copy constructing queues is disabled by default.
			// If you want copy-construction to be enabled, please define
			// BOOST_PLUS_ENABLE_QUEUE_COPYING
			BOOST_STATIC_ASSERT(false);
		}
		#endif

		/**
		 * 
		 */
		~queue()
		{
			// If you hit this assert then you still have readers or writers of queue, which you shouldn't.
			// Reorder your writers/readers so they get destroyed before the queue.
			BOOST_ASSERT(d.unique() == true);
		}



		/**
		 * Assign another queue to this one.
		 * The entire queue's contents will be copied,
		 * however whatever is in the buffer of a reader/writer
		 * will \b not be copied.
		 */
		#ifdef BOOST_PLUS_ENABLE_QUEUE_ASSIGNING
		queue<_Ty,threading_policy>& operator=(queue<_Ty,threading_policy>& _Right)
		{
			// Make a true copy of the implementation
			d = queue_ptr(new queue_private(_Right.d.get()));
		}
		#else
		queue<_Ty,threading_policy>& operator=(queue<_Ty,threading_policy>& _Right)
		{
			// Assigning queues is disabled by default.
			// If you want assigning- to be enabled, please define
			// BOOST_PLUS_ENABLE_QUEUE_COPYING
			BOOST_STATIC_ASSERT(false);
		}
		#endif



		/**
		 * Create a writer.
		 *
		 * @warning   using the same writer across multiple threads causes a race condition
		 * @warning   a writer should be destroyed before the queue
		 */
		template
		<
			template <typename> class buffering_policy
		>
		queue_writer<buffering_policy> writer()
		{
			return queue_writer<buffering_policy>( d );
		}

		/**
		 * Create a reader that can read from this queue.
		 *
		 * @warning   using the same reader across multiple threads causes a race condition
		 * @warning   it is the callers responsibility to not use the reader any more when the queue is destroyed
		 */
		template
		<
			template <typename> class buffering_policy
		>
		queue_reader<buffering_policy> reader()
		{
			return queue_reader<buffering_policy>( d );
		}




		/**
		 * Push an element onto the queue.
		 *
		 * @see queue_writer::push
		 */
		void push(const _Ty& _Val)
		{
			d->push(_Val);
		}

		/**
		 * Push a number of elements onto the queue.
		 *
		 * @see queue_writer::push
		 */
		void push(_List_Ty& _Vals)
		{
			d->push(_Vals);
		}



		/**
		 * Retrieve the first element from the queue.
		 * If there are elements, the first one is removed and returned.
		 * Otherwise an empty boost::optional is returned.
		 *
		 * @see queue_reader::pop
		 */
		_Opt_Ty pop()
		{
			return d->pop();
		}

		/**
		 * Retrieve and remove up to 'count' elements from the queue.
		 */
		_List_Ty pop(size_t _Count)
		{
			return d->pop(_Count);
		}

		/**
		 * Retrieve and remove all elements from the queue.
		 */
		_List_Ty pop_all()
		{
			return d->pop_all();
		}

		/**
		 * Retrieve the first element from the queue without removing it.
		 * If there are elements, the first one is returned.
		 * Otherwise an empty boost::optional is returned.
		 *
		 * @see queue_reader::peek
		 */
		_Opt_Ty peek() const
		{
			return d->peek();
		}



		/**
		 * Get the size of the queue.
		 *
		 * @see queue_reader::size
		 */
		size_type size()
		{
			return d->size();
		}

		/**
		 * Get the possible number of elements in the queue.
		 * The value returned may differ from the actual number, at the
		 * time of calling.
		 *
		 * @see queue_reader::sizeHint
		 */
		size_type sizeHint() const
		{
			return d->sizeHint();
		}

	private:

		/// The only member of this class is a shared pointer to
		/// the private implementation
		queue_ptr   d;
	};
	///////////////////////////////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////////////////////////////
